package leetcode.Hot100;

/**
 * @author Cheng Jun
 * Description: 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
 * @version 1.0
 * https://leetcode-cn.com/problems/maximal-square/
 * @date 2021/11/27 12:40
 */
public class maximalSquare {

    public static void main(String[] args) {
        System.out.println(maximalSquare(new char[][]{new char[]{'1', '1'}, new char[]{'1', '1'}}));
    }

    // 动态规划状态定义：sideMatrix[i][j] 表示 matrix[i][j] 能形成的最大正方形的边长
    // 动态规划初始值 ：初始值均为 0
    // 动态规划转移方程：sideMatrix[i][j] = min(sideMatrix[i][j-1], sideMatrix[i-1][j], sideMatrix[i-1][j-1])
    static int maximalSquare(char[][] matrix) {
        // 正方形最大边长
        int maxSide = 0;
        if (matrix.length == 0 || matrix[0].length == 0) return maxSide;
        int rows = matrix.length;
        int columns = matrix[0].length;
        // sideMatrix[i][j] 表示 matrix[i][j] 位置的元素能形成的最大的正方形边长
        int[][] sideMatrix = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    // 处于 matrix 的边缘位置
                    if (i == 0 || j == 0) {
                        sideMatrix[i][j] = 1;
                    } else {
                        sideMatrix[i][j] = Math.min(sideMatrix[i - 1][j - 1], Math.min(sideMatrix[i - 1][j], sideMatrix[i][j - 1])) + 1;
                    }
                }
                maxSide = Math.max(maxSide, sideMatrix[i][j]);
            }
        }
        return maxSide * maxSide;
    }
}
